Skip Navigation

Computer Science & Engineering

Course Specification

BACK

CSCE310 Course Specification

Catalog Description:

[IS] Theoretical concepts with programming assignments.
 Algorithm analysis, asymptotic notation, and solving recurrence relations.  Basic data structures (linked-lists, stacks, queues).  Advanced data structures and their associated algorithms, heaps, priority queues, hash tables, trees, binary search trees, and graphs.  Advanced sorting algorithms, and algorithmic techniques, randomization, divide and conquer, greedy algorithms, dynamic programming, and distributed algorithms.  Introduction to computability and NP-completeness.

Current Course Homepage:

http://www.cse.unl.edu/~ylu/csce310f05/index.htm

Textbook(s) and/or Other Required Materials:

  1. Anany Levitin, The Design and Analysis of Algorithms, supplemented as necessary with handouts.

Prerequisites by Topic:

  1. Mastery of data structures and operations for lists, stacks, queues, trees, graphs. Abstract data types. Discrete mathematics topics including induction and recursion, set theory, elementary combinatorics, elementary graph theory.
  2. Familiarity with recursive algorithms and recurrence relations.
  3. Exposure to complexity analysis.

Course Objectives:

  1. Mastery of algorithmic approaches including greedy method and divide-and-conquer. A variety of common algorithms for searching and sorting, hashing, heaps; DFS, BFS, and other elementary algorithms on trees and graphs. Theoretic and empirical complexity analysis, including solving summations and recurrences.
  2. Familiarity with problems on graphs and advanced graph algorithms; algorithm correctness.
  3. Exposure to dynamic programming, NP Completeness, decidability.

Topics Covered:

It is expected that specific algorithms, problem solving techniques, and complexity analysis will be taught as text book topics and strongly reinforced with substantial theoretical and programming assignments, including theoretical and empirical analyses of complexity. "Mastery" implies ability to apply the knowledge gained in innovative and novel ways. This requires practice.
  1. Algorithm analysis and asymptotic notation, revisiting selection sort and bubble sort from CSCE 156 as examples.
  2. Solving recurrences: A variety of methods including the master method.
  3. Heaps and priority queues, heapsort.
  4. ?(n log n) lower bound for sorting; radix sort.
  5. Hashing and hash tables.
  6. Search trees: eg. binary search trees, balanced search trees.
  7. Graph algorithms: DFS, BFS, LBFS, applications to topological sort and strongly connected components, spanning trees.
  8. Divide-and-conquer algorithms: merge sort, quick sort, closest pair of points, binary searching of a sorted list (from CSCE 156).
  9. Greedy algorithms: Greedy choice and optimal substructure properties, e.g. fractional knapsack, Huffman codes, MST.
  10. Introduction to dynamic programming: optimal substructure property, shortest paths algorithms, 0-1 knapsack problem.
  11. Basic string matching algorithms.
  12. Introduction to NP-Completeness, and decidability.

Relationship of Course to Program Objectives:

Contributes to Program Objectives 1 and 2 throught Program Outcome 2.b, and to Program Objectives 3 and 4 through Program Outcome 3.b.

Contribution of Coruse to Meeting the Professional Component:

Contributes to Criterion 4(b) through the study of the design and analysis of algorithms. AL1, AL2. AL3 is in 156.

Class/Laboratory Schedule:

Lecture: 45 hours = 3 hours/week for 15 weeks